1. Field of the Invention
The present invention relates to ciphering algorithms, especially of Data Encryption Standard (DES) type, executed by integrated circuits. The present invention more specifically relates to the protection of the execution of a DES algorithm against an attack by differential power analysis (DPA) of the circuit which executes the algorithm.
2. Discussion of the Related Art
DES or triple DES algorithms are symmetrical ciphering algorithms (with a secret key) used in cryptography, for example, to cipher data before transmission over unprotected supports (Internet, connection between a smart card and a card reader, between a processor and an external memory, etc.). Such algorithms are described, for example, in standards FIPS PUB 46-2 (DES) and FIPS PUB 46-1, and operating modes (known as electronic codebook—ECB, cipher block chaining—CBC, cipher feedback—CFB, output feedback—OFB) are described in FIPS PUB 81.
Such algorithms perform a ciphering by blocks (of 64 bits) by using keys (of 64 bits for the DES and of 128 for the triple DES) from which are derived 48-bit sub-keys. The deciphering is performed from the same key (symmetrical algorithm). In the following description, the DES algorithm will be taken as an example.
FIG. 1 is a schematic block diagram illustrating the successive steps of a DES algorithm to which the present invention more specifically applies.
A block of data to be ciphered (noted M) is submitted to an initial permutation IP (block 11), then to 16 iterations of a calculation depending on a key, noted KEY, and finally to a permutation inverse to the initial permutation, noted IP−1 (block 12).
The calculation depending on key KEY may be expressed with the following notations:
i, the rank of the iteration ranging between 1 and 16 (initialization of i, block 13, i=1);
Ki, a 48-bit block extracted from 64-bit key KEY (DES example) used in the ciphering function of rank i;
LiRi, a 64-bit data block, resulting from the application of a function f to a block Ri-1 (block 14) with sub-key Ki, formed of a left-hand 32-bit word or sub-block Li and of a right-hand 32-bit word or sub-block Ri; and
f, a ciphering function.
With the above notations, the result of initial permutation 11 is a block L0R0 and each iteration or turn from 1 to 16 applies:
Li (block 16)=Ri-1 (block 14); and
Ri (block 17)=Li-1(+)f(Ri-1, Ki), where (+) designates a bit-to-bit addition modulo 2 (block 18), that is, a bit-to-bit XOR, combining result f(Ri-1, Ki) with word Li-1 (block 19).
As long as the last turn has not been reached (output N of block 15, i=16 ?), index i is incremented (block 20, i=i+1) and the next iteration is applied. The result of the last iteration is a block L16R16 (output Y of block 15) which, after having been turned (block 25) into block R16L16, is submitted to the inverse permutation IP−1 12 to provide a ciphered block designated as M′.
Function f comprises three successive steps:
a first step is an expansion, noted E (block 21) of the 32 bits of sub-block Ri-1 into 48 bits to combine them, by a bit-to-bit XOR function 22 (+), with the 48 bits of sub-key Ki of the concerned iteration. This expansion and combination provides 8 six-bit groups;
a second step applies to the 48 bits resulting from the preceding step a substitution table, noted S (block 23) or SBOX. In this step, each six-bit group resulting from the previous expansion is transformed, by one of eight substitution functions (primitive functions) to obtain eight four-bit groups, that is, 32 bits again;
a third step is a permutation, designated as P (block 24), of the 32 bits resulting from the previous step. This permutation provides a 32-bit result sub-block corresponding to the result of function f.
Each sub-key Ki is obtained (block 30) by applying a primitive key function KS to key KEY, function KS depending on rank i of the iteration, that is: Ki=KS(i, KEY).
The details of primitive functions KS, S, and P, as well as of function E, are described in the above-mentioned standards.
The deciphering is performed by submitting a block to be deciphered M′ to permutation IP, then to calculation iterations identical to those of the ciphering, with the sole difference that the sub-keys are used in an inverse order (it is started from sub-key K16 to end with sub-key K1). The first block resulting from permutation IP is block L16R16 and the block resulting from the last iteration to be submitted to permutation IP−1 is block R0L0. Permutation IP−1 provides deciphered block M.
A weakness of DES-type algorithms appears in attacks by differential power analysis of a circuit executing the algorithm. Such attacks consist of making assumptions about the key to correlate an intermediary result with the integrated circuit power consumption. Such attacks enable discovering the secret key. Indeed, function f is known (DES standard), and so are the input data M (or M′) applied to the algorithm. When making an assumption on a portion of sub-key K, part of the bits of an intermediary result LiRi is obtained. If a correlation between this part of the bits and the circuit power consumption is obtained at a given time, the assumption about the key is verified. Computation means enable hackers to make assumptions in a sufficient number, and thus to hack the secret of the circuit (the key).
The key is generally stored in a secure circuit area, for example, in an integrated circuit customization phase. Its loading into the algorithm execution cell is performed in protected fashion, for example, by applying the methods described in U.S. published patents application 2001/0054163 and U.S. Pat. No. 7,166,783.
A first known solution, to attempt protecting a secret handled by a DES algorithm, is to mask the execution by introducing random numbers into the iterations. This solution has the disadvantage of requiring a modification of the actual algorithm.
A second known solution is to mask the algorithm execution with the secret key by having it execute among several executions (on the order of some ten) using dummy keys. These keys are permanently stored in a non-volatile memory associated with the algorithm execution processor or directly hardwired in the circuit. The real key is generally written on customization of the circuit (for example, of the smart card) by a person different from the circuit manufacturer, in a generally inaccessible area (secure circuit area). Thus, a hacker cannot know, when an assumption about the key is verified, whether the right key or not has been used. A disadvantage of this solution is that, to preserve the masking, it is necessary to protect all keys (the fake ones as well as the right ones) on loading thereof into the algorithm execution cell. This takes time and lengthens, in a way incompatible with the desired fast data handling, the execution of this algorithm. Another disadvantage of this solution is that it introduces white noise only, thus easily filterable by the pirate.